package acm.test;

public class 组合 {

    static int m, k, number = 0, res = 0;

    public static void dfs(int now, int yu, int ci) {
        if (ci == 1 && now <= yu) {
            res++;
            return;
        }
        if (number == m && ci == 0) {
            res++;
            return;
        }
        for (int i = now; i <= yu; i++) {
            if (yu - i >= now) {
                number += i;
                dfs(i, yu - i, ci - 1);
                number -= i;
            }
        }
    }

    public static int fun1(int argN, int argK) {
        number = 0;
        res = 0;
        m = argN;
        k = argK - 1;
        for (int i = 1; i <= m / 2; i++) {
            if (i <= m - i) {
                number += i;
                dfs(i, m - i, k);
                number -= i;
            }
        }
        return res;
    }

    //递归版本

    /**
     * 切蛋糕问题：组合问题+分支界限
     */
    public static int fun2(int curr, int n, int k) {
        if (k == 1) {  //终止条件
            return 1;
        }
        int res = 0;
        while (curr <= n / k) {  //确定范围
            res += fun2(curr, n - curr, k - 1);    //当前选择与之后选择的依赖关系
            curr++;
        }
        return res;
    }

    //改动态规划
    public static int fun3(int n, int k) {
        int[][][] dp = new int[k + 1][n + 1][n / k];
        for (int[] ints : dp[1]) {
            for (int i = 0; i < ints.length; i++) {
                ints[i] = 1;
            }
        }
        return 0;
    }

    //人工智能的动态规划
    public static int fun2(int n, int k) {
        int[][] dp = new int[k + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            dp[1][i] = 1;
        }
        for (int i = 2; i <= k; i++) {
            for (int j = 1; j <= n; j++) {
                for (int l = 1; l <= j / i; l++) {
                    dp[i][j] += dp[i - 1][j - l];
                }
            }
        }
        return dp[k][n];
    }

    public static void main(String[] args) {
//        System.out.println(fun2(1,7,3));
        System.out.println(fun1(7, 3));
        System.out.println(fun3(7, 3));
//        test();
    }

    public static void test() {
        int count = 10000;
        while (count-- > 0) {
            int n = (int) (Math.random() * 194 + 6);
            int k = (int) Math.random() * 5 + 2;
            int fun1 = fun1(n, k);
//            int fun2 = fun2(n, k);
            int fun3 = fun2(1, n, k);
            if (fun1 != fun3) {
                System.out.println("n:" + n + ",k:" + k);
                System.out.println("预期输出" + fun1);
                System.out.println("实际输出" + fun3);
            }
        }
    }
}
